package dp.practice1;

public class Main {
    public static void main(String[] args) {
        int[][] triangle = {
                new int[]{2},
                new int[]{3, 4},
                new int[]{6, 5, 7},
                new int[]{4, 1, 8, 3}
        };
        System.out.println(minimumTotal(triangle));
    }

    public static int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle.length == 0)
            return 0;
        int len = triangle.length;
        //用来记录每一步的状态
        int[][] cost = new int[len][len];
        cost[0][0] = triangle[0][0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                //计算上一个状态的时候，防止出现越界问题
                int lower = Math.max(0, j - 1);
                int upper = Math.min(j, triangle[i - 1].length - 1);
                //状态转移方程
                cost[i][j] = Math.min(cost[i - 1][lower], cost[i - 1][upper]) + triangle[i][j];
            }
        }
        int minCost = Integer.MAX_VALUE;
        for (int k = 0; k < triangle[len - 1].length; k++) {
            minCost = Math.min(minCost, cost[len - 1][k]);
        }
        return minCost;
    }
}
